package com.atcumt.Write.sort;

import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Arrays;

/**
 * 快速排序
 * 通过一趟排序将待排记录分隔成独立的两部分，
 * 从前面往后面找比基准数大的，从后面往前找到比基准数小的，然后进行对换
 * 分别对这两部分记录继续进行排序，以达到整个序列有序
 */
public class QuickSort {

    private static void quickSort (int[] arr, int left, int right) {

        if (left < right) {
            int i = left, j = right, x = arr[left]; // 第一个坑 arr[left] 为基准数
            while (i < j) {
                while (i < j && arr[j] > x) {
                    j--; // j--由后向前找比它小的数，找到后挖出此数填前一个坑a[i]中。
                }
                if (i < j) {
                    arr[i++] = arr[j];
                }
                while (i < j && arr[i] < x) {
                    i++; // i++由前向后找比它大的数，找到后挖出此数填到前一个坑a[j]中
                }
                if (i < j) {
                    arr[j--] = arr[i];
                }
            }
            arr[i] = x; // 直到 i==j ，将基准数填入a[i]中
            quickSort(arr, left, i - 1);
            quickSort(arr, i + 1, right);
        }
    }

    public static void main(String[] args) throws IOException {
        BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
        int[] nums = Arrays.stream(br.readLine().split(" ")).mapToInt(Integer::valueOf).toArray();
        quickSort(nums, 0, nums.length - 1);
        System.out.println(Arrays.toString(nums));
    }
}
